package com.hqq.leetcode.tree;

import com.hqq.exercise.tree.TreeNode;
import com.hqq.exercise.tree.TreeNodeUtil;

/**
 * ArrayToBST 把排序数组转换为高度最小的二叉搜索树
 * 题目描述:
 * 给一个排序数组（从小到大），将其转换为一棵高度最小的排序二叉树
 * 样例输入:
 * [1,2,3,4,5,6,7]
 * 样例输出:
 * 答案不唯一
 * -----4
 * ---/   \
 * --2     6
 * -/ \    / \
 * 1   3  5   7
 * 思路:
 * 二分查找
 * Created by heqianqian on 2017/9/12.
 */
public class ArrayToBST {

    public static void main(String[] args) {
        int[] array = new int[]{1, 2, 3, 4, 5, 6, 7};
        ArrayToBST arrayToBST = new ArrayToBST();
        TreeNode node = arrayToBST.sortedArrayToBST(array);
        TreeNodeUtil.preOrderTraversal(node);
    }

    public TreeNode sortedArrayToBST(int[] array) {
        // write your code here
        if (array == null || array.length == 0) {
            return null;
        }
        return constructTree(array, 0, array.length-1);
    }

    private TreeNode constructTree(int[] array, int start, int end) {
        if (start < 0 || end > array.length || start > end) {
            return null;//递归出口
        }
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(array[mid]);
        root.left = constructTree(array, start, mid - 1);
        root.right = constructTree(array, mid + 1, end);
        return root;
    }
}
